package Test01;

import org.junit.Test;

import java.util.*;

/**
 * @author 29349
 */
public class Test01 {
    @Test
    public void xx() {
        int[] ints=new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        // List<List<Integer>> lists = combinationSum(ints, 7);
        System.out.println(trap3(ints));
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
    //接雨水:暴力破解：
    public int trap(int[] height) {
        int sum=0;
        int length=height.length;
        for (int i = 1; i < length-1; i++) {
            int max_left=0,max_right=0;
            for (int j = i; j >=0; j--) {
                max_left=Math.max(max_left,height[j]);
            }
            for (int j = i; j < length; j++) {
                max_right=Math.max(max_right,height[j]);
            }
            sum+=Math.min(max_left,max_right)-height[i];
        }
        return sum;
    }
    //接雨水:动态规划：
    public int trap1(int[] height){
        if (height == null || height.length == 0) {
            return 0;
        }
        int len=height.length;
        int [] lefts=new int[len];
        int [] rights=new int[len];
        int sum=0;
        rights[len-1]=height[len-1];
        lefts[0]=height[0];
        for (int i = 1; i < len; i++) {
        lefts[i]=Math.max(lefts[i-1],height[i]);
        }
        for (int i = len-2; i >=0; i--) {
            rights[i]=Math.max(rights[i+1],height[i]);
        }
        for (int i = 0; i < len; i++) {
            sum+=Math.min(lefts[i],rights[i])-height[i];

        }
        return sum;
    }
    //接雨水:栈操作：
    public int trap2(int[] height){
        int sum=0;
        if (height == null || height.length == 0) {
            return 0;
        }
        int len=height.length;
        Stack<Integer> stack=new Stack<>();
        int left=0;
       while (left<len) {
           while (!stack.isEmpty() && height[stack.peek()] < height[left]) {
               int top = stack.pop();
               //当弹出的位置为第一位时，将不能存下水。跳出内循环。
               if (stack.isEmpty()) {
                   break;
               }
               //获取当前位置和存水的宽度。
               int distance = left - stack.peek() - 1;
               //通过从两边界获取最小值来取得高度
               int bounded_height = Math.min(height[left], height[stack.peek()]) - height[top];
               sum += distance * bounded_height;
           }
           stack.push(left++);
       }
        return sum;
    }
    //接雨水:双指针：
    public int trap3(int[] height){
        int sum=0;
        if (height == null || height.length == 0) {
            return 0;
        }
        int len=height.length;
        int left=0,right=len-1;
        int left_max=0,right_max=0;
        while (left<right){
            if(height[left]<height[right]){
                if(height[left]>=left_max){
                    left_max=height[left];
                }else {
                    sum+=left_max-height[left];
                }
                left++;
            }else {
                if(height[right]>=right_max){
                    right_max=height[right];
                }else {
                    sum+=right_max-height[right];
                }
                right--;
            }
        }
        return sum;
    }
    //字符串相乘：
    public String multiply(String num1, String num2) {

        StringBuilder stringBuilder=new StringBuilder();
        return "";
    }
    public int jump(int[] nums) {
        int sum=0;
        int x=nums[0];
        for (int i = 0; i <nums.length ; i++) {
            for(int j=0;j<x;j++){

            }
        }
        return sum;
    }
    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
   @Test
    public void π_2(){
        double y=1.0;
        for(int i=0;i<=80;i++){
            double π=3*Math.pow(2, i)*y;
            System.out.println("第"+i+"次切割,为正"+(6+6*i)+"边形，圆周率π≈"+π);
            y=Math.sqrt(2-Math.sqrt(4-y*y));
        }

    }
    public static double rand_pi(int n) {
        int numInCircle = 0;
        double x, y;
        double pi;
        for(int i=0;i < n; i++){
            x = Math.random();
            y = Math.random();
            if(x * x + y * y < 1) {
                numInCircle++;
            }
        }
        pi = (4.0 * numInCircle) / n;
        return pi;
    }

    public static void main(String[] args) {
        System.out.println(rand_pi(10));  //改变参数值
        System.out.println(rand_pi(100));  //改变参数值
        System.out.println(rand_pi(1000));  //改变参数值
        System.out.println(rand_pi(10000));  //改变参数值
        System.out.println(rand_pi(100000));  //改变参数值
        System.out.println(rand_pi(1000000));  //改变参数值
        System.out.println(rand_pi(10000000));  //改变参数值
        System.out.println(rand_pi(100000000));  //改变参数值
        System.out.println(rand_pi(1000000000));  //改变参数值
    }
    @Test
    public void maxSubArray() {
        int[] nums=new int[]{-2,1,-3,4,-1,2,1,-5,4};
      /*  int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        System.out.println(res);*/
        int now=nums[0];
        for (int i = 1; i < nums.length; i++) {
             if(now<nums[i]){
                 now=nums[i];
             }else {
                 now+=nums[i];
                 nums[i]=now;
             }
        }
        int max=0;
        for (int y:nums
             ) {
            max=Math.max(y,max);
        }
        System.out.println(max);
    }
    public void solveNQueens() {
        int n=4;
        List<List<String>> lists=new ArrayList<>();
         int[][] ints = new int[4][4];


    }
    @Test
    public void canJump() {
        int[] nums=new int[]{2,3,1,1,4};
       /* boolean[] booleans=new boolean[nums.length];
        booleans[0]=true;
        for (int i = 0; i < nums.length; i++) {
            if(booleans[i]){
                int x=nums[i];
                if(nums[i]+i>=nums.length){
                    System.out.println(true);
                    return;
                }else {
                    for (int j = 0; j <=i+nums[i] ; j++) {
                        if(!booleans[j]){

                        }
                        booleans[j]=true;
                    }

                }
            }else {
                System.out.println(false);
                return;
            }
        }
        if(booleans[nums.length-1]){
            System.out.println(true);
            return;
        }
        return;*/
        int reach =nums[0];
        for (int i=0;i<nums.length;i++){
            if(reach<i){
                System.out.println(false);
                return;
            }else {
                reach=Math.max(reach,i+nums[i]);
            }
            if(reach>=nums.length){
                System.out.println(true);
                return;
            }
        }
    }
    @Test
    public void uniquePaths() {
        int m=7,n=3;
        int[][] dp=new int[m][n];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0]=1;
        }
        Arrays.fill(dp[0], 1);
        for (int i=1;i<dp.length;i++){
            for (int j=1;j<dp[i].length;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        System.out.println(dp[m-1][n-1]);
        return;
    }
    @Test
    public void uniquePathsWithObstacles() {
        int[][] obstacleGrid=new int[][]{{1,0}};
        int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < dp.length; i++) {
            if(obstacleGrid[i][0]==1){
                dp[i][0]=0;
            }else{
                dp[i][0]=dp[i-1][0];
            }
        }
        for (int i = 0; i < dp[0].length; i++) {
            if(obstacleGrid[0][i]==1){
                dp[0][i]=0;
            }else{
                dp[0][i]=dp[0][i-1];
            }
        }
        for (int i=1;i<obstacleGrid.length;i++){
            for (int j=1;j<obstacleGrid[i].length;j++){
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                }else {
                    dp[i][j]=dp[i-1][j-1];
                }
            }
        }
        System.out.println(dp[obstacleGrid.length - 1][obstacleGrid[0].length-1]);
    }
    @Test
    public void minPathSum() {
        int[][] grid=new int[][]{ {1,3,1},{1,5,1},{4,2,1}};
        if(grid==null||grid.length==0){
            System.out.println("error");
            return;
        }
        int[][] dp=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for (int i = 1; i < dp.length; i++) {
           dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i < dp[0].length; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <dp[0].length ; j++) {
                dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        System.out.println(dp[dp.length-1][dp[0].length-1]);
    }
    @Test
    public void climbStairs() {
        int n=3;
        if(n == 1){return;}
        if(n == 2){return ;}
        int a = 1, b = 2, temp;
        for(int i = 3; i <= n; i++){
            temp = a+b;
            a = b;
            b = temp ;
        }
        System.out.println(b);
        return;

    }
    @Test
    public void minDistance() {
        String word1="intention",  word2="tnt";
        int l1=word1.length(),l2=word2.length();
        if(l1*l2==0){
            System.out.println(l1+l1);
            return;
        }
        int[][]dp=new int[l1+1][l2+1];
        for (int i = 0; i <= l1; i++) {
            dp[i][0]=i;
        }
        for (int i = 0; i <= l2; i++) {
            dp[0][i]=i;
        }
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <=l2; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        System.out.println(dp[l1][l2]);
    }
    public void inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> stack=new LinkedList<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            list.add(root.val);
            root=root.right;
        }
    }
    class TreeNode {
     int val;
     TreeNode left;
         TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
    @Test
    //不同的二叉搜索树 II
    public void generateTrees() {
        int n=9;
        if(n==0){
            System.out.println("null");
            return;
        }
        List<TreeNode> list=   findAll(1,n);
        for (TreeNode l:list) {
            System.out.println(l);
        }
    }
    private List<TreeNode> findAll(int i, int n) {
        List<TreeNode> list=new LinkedList<>();
        if(i>n){
            list.add(null);
            return list;
        }
        for (int j = i; j <=n; j++) {
            List<TreeNode> left=findAll(i,j-1);
            List<TreeNode> right=findAll(j+1,n);
            for (TreeNode leftNode: left) {
                for (TreeNode rightNode: right) {
                    TreeNode root=new TreeNode(j);
                    root.left=leftNode;
                    root.right=rightNode;
                    list.add(root);
                }
            }
        }
        return list;
    }
    @Test
    public void t() {
        isInterleave("","","");

    }
    public void isInterleave(String s1, String s2, String s3) {
        int l1=s1.length(),l2=s2.length(),l3=s3.length();
        if((l1+l2)!=l3){
            System.out.println(false);
            return;
        }
        boolean[][] ll=new boolean[l1+1][l2+1];
        ll[0][0]=true;
        for (int i = 1; i <=l1; i++) {
        ll[i][0]=ll[i-1][0]&(s1.charAt(i-1)==s3.charAt(i-1));
        }
        for (int i = 1; i <=l2; i++) {
            ll[0][i]=ll[0][i-1]&(s2.charAt(i-1)==s3.charAt(i-1));
        }
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <=l2 ; j++) {
                ll[i][j]=(ll[i][j-1]&(s2.charAt(j-1)==s3.charAt(i+j-1)))||
                        (ll[i-1][j]&(s1.charAt(i-1)==s3.charAt(i+j-1)));
            }
        }
        for (int i = 0; i <= l1; i++) {
            for (int j = 0; j <= l2; j++) {
                System.out.print(ll[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(ll[l1][l2]);
    }
    public int search(int[] nums, int target) {
        int len=nums.length;
        if(len<=0){
            return -1;
        }
        int l=0,r=len-1;
        while (l<r){
            int mid=l+(r-l)/2;
            if(mid<target){
                l=mid;
            }else if(mid>target){
                r=mid;
            }else {
                return mid;
            }
        }
    return -1;
    }
    public int searchInsert(int[] nums, int target) {
 int index=0;
 int l=0,r=nums.length-1;
 while (l<r){
     int mid=l+(r-l)/2;
     if(nums[mid]<target){
         l=mid+1;
     }else if(nums[mid]>target){
         r=mid;
         index=mid;
     }else {
         return mid;
     }
 }
 return index;
    }
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists=new ArrayList<>();
    List<Integer> list1=new ArrayList<>();
    list1.add(1);lists.add(list1);
    if(numRows==1){
        return lists;
    }
        for (int i = 1; i <=numRows; i++) {
            List<Integer> list2=new ArrayList<>();
            list2.add(1);
            for (int j = 1; j <i ; j++) {
                list2.add(list1.get(j-1)+list1.get(j));
            }
            list2.add(1);
            lists.add(list2);
            list1=list2;
        }
        return lists;
    }
    @Test
    public void getRow() {
        int rowIndex=3;
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add(0);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        System.out.println(row);
    }
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        int x=0,x1=1,target=0;
        for (int i = 0; i < n; i++) {
        target=x;
        x=x1;
        x1=x+target;
        }
return x1;
    }
    public int tribonacci(int n) {
    int T0 = 0, T1 = 1, T2 = 1;
    if(n==0){
        return 0;
    }
    if(n<=2){
        return 1;
    }
    int target=0;
        for (int i = 3; i <n ; i++) {
            target=T0+T1+T2;
            T0=T1;T1=T2;T2=target;
        }
        return target;
    }
    public boolean containsDuplicate(int[] nums) {
        if(null==nums||nums.length==0){
            return true;
        }
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return false;
            }
            set.add(nums[i]);
        }
        return true;
    }
    public int minimumTotal(List<List<Integer>> triangle) {
    int len=triangle.size();
    int[][] dp=new int[len][len];
        for (int i = 0; i <triangle.get(len-1).size() ; i++) {
            dp[len-1][i]=triangle.get(len-1).get(i);
        }
        for (int i = len-2; i >=0 ; i++) {
            List<Integer> list1=triangle.get(i);
            List<Integer> list2=triangle.get(i+1);
            for (int j = 0; j <list1.size() ; j++) {
                dp[i][j]=Math.min(list2.get(j),list2.get(j+1))+list1.get(j);
            }
        }
        return dp[0][0];
    }
    public int[] reversePrint(ListNode head) {
       /* List<Integer> list=new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head=head.next;
        }
        int[] res=new int[list.size()];
        for (int i = 0; i <list.size(); i++) {
            res[i]=list.get(list.size()-i-1);
        }
        return res;*/
        Stack<ListNode> stack=new Stack<>();
        while (head!=null){
            stack.push(head);
            head=head.next;
        }
        int size=stack.size();
        int[] res=new int[size];
        for (int i = 0; i <size ; i++) {
            res[i]=stack.pop().val;
        }
        return res;
    }
    public ListNode reverseList(ListNode head) {
    ListNode pre=null;
    ListNode next=head;
    while (next!=null){
        ListNode xx = next.next;
        next.next = pre;
        pre = next;
        next = xx;

    }
    return pre;
    }
    @Test
    public void minCostClimbingStairs() {
        int[] cost=new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    int dp[]=new int[cost.length];
    dp[0]=cost[0];dp[1]=cost[1];
        for (int i = 2; i <cost.length; i++) {
                if(cost.length-i<2){
                    dp[i]=Math.min(dp[i-1],dp[i-2]+cost[i]);
                    break;
                }
                dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];

        }
        System.out.println(dp[cost.length - 1]);
    }
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i <nums.length ; i++) {
            int temp=nums[i];
            nums[i]=temp*temp;
        }
        Arrays.sort(nums);
        return nums;
    }
    public void rotate(int[] nums, int k) {
    int [] xx=new int[k];
        for (int i = 0; i <k ; i++) {
            xx[i]=nums[nums.length-1-i];
        }
        for (int i = nums.length-1; i >=0; i--) {
            if(i-k-1>=0){
                nums[i]=nums[i-k-1];
            }else {
             nums[i]=xx[i];
            }
        }
    }
    public int purchasePlans(int[] nums, int target) {
            int mod=100000007;
            int ans=0;
            Arrays.sort(nums);
            int l=0,r=nums.length-1;
            while (l<r){
                if(nums[l]+nums[r]>target){r--;}
                else {
                    ans+=(r-l);
                    l++;
                }
                ans%=mod;
            }
            return ans;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class ListNode {
     int val;
    ListNode next;
     ListNode(int x) { val = x; }
 }